#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5, maxa = 1e6 + 5;
const ll INF = 1e18;
int n, A[maxn];
ll pre[maxn];
ll dp[maxn], mx[maxa];
void solve() {
    scanf("%d", &n);
    mx[0] = -INF;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &A[i]);
        mx[A[i]] = -INF;
    }
    A[0] = A[n + 1] = 0;
    pre[0] = pre[1] = 0;
    for (int i = 2; i <= n + 1; i++) {
        pre[i] = pre[i - 1] + (A[i] == A[i - 1]) * A[i];
    }
    for (int i = 0; i <= n + 1; i++) {
        dp[i] = -INF;
    }
    dp[0] = 0;
    dp[1] = 0;
    mx[A[1]] = 0;
    set<pair<ll, int>> s;
    s.insert({0, A[1]});
    for (int i = 2; i <= n + 1; i++) {
        auto it = s.begin();
        if (it->second == A[i]) {
            it++;
        }
        if (it != s.end()) {
            dp[i] = max(dp[i], -it->first - (A[i] == A[i - 1]) * A[i]);
        }
        dp[i] = max(dp[i], mx[A[i]] + A[i] - (A[i] == A[i - 1]) * A[i]);
        if (dp[i] > mx[A[i - 1]]) {
            s.erase({-mx[A[i - 1]], A[i]});
            mx[A[i - 1]] = dp[i];
            s.insert({-mx[A[i - 1]], A[i]});
        }
        // cout << dp[i] << ' ';
    }
    // cout << '\n';
    printf("%lld\n", pre[n] + dp[n + 1]);
}
int main() {
    freopen("color.in", "r", stdin);
    freopen("color.out", "w", stdout);
    int T;
    scanf("%d", &T);
    while (T--) {
        solve();
    }
    return 0;
}